/**
 * Author: Bryan Guner
 * Dijkstra's Algorithm implementation in JavaScript
 * Dijkstra's Algorithm calculates the minimum distance between two nodes.
 * It is used to find the shortes path.
 * It uses graph data structure.
 */

function createGraph( V, E ) {
  // V - Number of vertices in graph
  // E - Number of edges in graph (u,v,w)
  const adjList = [] // Adjacency list
  for ( let i = 0; i < V; i++ ) {
    adjList.push( [] )
  }
  for ( let i = 0; i < E.length; i++ ) {
    adjList[ E[ i ][ 0 ] ].push( [ E[ i ][ 1 ], E[ i ][ 2 ] ] )
    adjList[ E[ i ][ 1 ] ].push( [ E[ i ][ 0 ], E[ i ][ 2 ] ] )
  }
  return adjList
}

function djikstra( graph, V, src ) {
  const vis = Array( V ).fill( 0 )
  const dist = []
  for ( let i = 0; i < V; i++ ) dist.push( [ 10000, -1 ] )
  dist[ src ][ 0 ] = 0

  for ( let i = 0; i < V - 1; i++ ) {
    let mn = -1
    for ( let j = 0; j < V; j++ ) {
      if ( vis[ j ] === 0 ) {
        if ( mn === -1 || dist[ j ][ 0 ] < dist[ mn ][ 0 ] ) mn = j
      }
    }

    vis[ mn ] = 1

    graph[ mn ].forEach( edge => {
          if ( vis[ edge[ 0 ] ] === 0 && dist[ edge[ 0 ] ][ 0 ] > dist[ mn ][ 0 ] + edge[ 1 ] ) {
            dist[ edge[ 0 ] ][ 0 ] = dist[ mn ][ 0 ] + edge[ 1 ]
            dist[ edge[ 0 ] ][ 1 ] = mn
      }
    } );
  }

  return dist
}

const V = 9
const E = [
  [ 0, 1, 4 ],
  [ 0, 7, 8 ],
  [ 1, 7, 11 ],
  [ 1, 2, 8 ],
  [ 7, 8, 7 ],
  [ 6, 7, 1 ],
  [ 2, 8, 2 ],
  [ 6, 8, 6 ],
  [ 5, 6, 2 ],
  [ 2, 5, 4 ],
  [ 2, 3, 7 ],
  [ 3, 5, 14 ],
  [ 3, 4, 9 ],
  [ 4, 5, 10 ]
]

const graph = createGraph( V, E )
const distances = djikstra( graph, V, 0 )

/**
 * The first value in the array determines the minimum distance and the
 * second value represents the parent node from which the minimum distance has been calculated
 */

console.log( distances )
